class Node():
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree():
    def __init__(self):
        self.root = None
        self.queue = []

    def insert_node(self, elem):
        new_node = Node(elem)
        self.queue.append(new_node)
        if self.root is None :
            self.root = new_node
        else :
            if self.queue[0].lchild is None :
                self.queue[0].lchild = new_node
            else:
                self.queue[0].rchild = new_node
                self.queue.pop(0)

    def preorder(self,current_node:Node):
        if current_node:
            print(current_node.elem,end=' ')
            self.preorder(current_node.lchild)
            self.preorder(current_node.rchild)

    def midorder(self,current_node:Node):
        if current_node:
            self.midorder(current_node.lchild)
            print(current_node.elem, end=' ')
            self.midorder(current_node.rchild)

    def lastorder(self,current_node:Node):
        if current_node:
            self.lastorder(current_node.lchild)
            self.lastorder(current_node.rchild)
            print(current_node.elem,end=' ')


if __name__ == '__main__':
    tree = Tree()
    for i in range(1,11):
        tree.insert_node(i)

    tree.preorder(tree.root)
    print()

    tree.midorder(tree.root)
    print()

    tree.lastorder(tree.root)
